package Easy.q2;

import java.util.ArrayList;

/*
* 给你两个 非空 的链表，表示两个非负的整数。
* 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class q2 {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        ArrayList<Integer> list3 = new ArrayList<>();
        list1.add(1);
        list1.add(3);
        list1.add(3);
        list1.add(9);
        list1.add(9);
        list1.add(9);
        list2.add(9);
        list2.add(9);
        list2.add(9);
        System.out.println(list1);
        System.out.println(list2);
        list3 = twoSum(list1, list2);
        System.out.println(list3);

    }

    public static ArrayList<Integer> twoSum(ArrayList<Integer> list1, ArrayList<Integer> list2) {
        ArrayList<Integer> sum = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        int size = Math.max(list1.size(), list2.size());
        int higher = 0;
        for (int i = 0; i < size + 1; i++) {
            int a = list1.size() >= i + 1 ? list1.get(i) : 0;
            int b = list2.size() >= i + 1 ? list2.get(i) : 0;
            sum.add((a + b + higher) % 10);
            higher = (a + b + higher) / 10;
        }
        if (sum.get(sum.size() - 1) == 0) {
            sum.remove(sum.size() - 1);
        }
        return sum;
    }
}

